from sortedcontainers import SortedList
from bisect import bisect_right


class IntervalSet:
    def __init__(self):
        # Store non-overlapping intervals [(l, r), ...]
        self.intervals = SortedList()
        self.total_length = 0  # Sum of all interval lengths

    def _find_left(self, x):
        """Find index of interval possibly containing x (or its left neighbor)."""
        i = bisect_right(self.intervals, (x, float('inf')))
        if i:
            i -= 1
        return i

    def add(self, l, r):  # noqa: E741
        """Insert interval [l, r) and merge with overlapping/adjacent ones."""
        if l >= r:
            return

        i = self._find_left(l)
        new_l, new_r = l, r

        merged = []
        while i < len(self.intervals):
            il, ir = self.intervals[i]
            if ir < new_l:
                i += 1
                continue
            if il > new_r:
                break
            # Merge
            new_l = min(new_l, il)
            new_r = max(new_r, ir)
            merged.append(i)
            i += 1

        # Remove merged intervals and update total_length
        for j in reversed(merged):
            il, ir = self.intervals[j]
            self.total_length -= (ir - il)
            del self.intervals[j]

        # Add new merged interval
        self.intervals.add((new_l, new_r))
        self.total_length += (new_r - new_l)

    def remove(self, l, r):  # noqa: E741
        """Remove interval [l, r) and adjust possible splits."""
        if l >= r:
            return

        i = self._find_left(l)
        updates = []
        while i < len(self.intervals):
            il, ir = self.intervals[i]
            if il >= r:
                break
            if ir <= l:
                i += 1
                continue

            # Remove current interval
            self.total_length -= (ir - il)
            del self.intervals[i]

            # Add back non-overlapping parts
            if il < l:
                updates.append((il, l))
            if ir > r:
                updates.append((r, ir))

        for iv in updates:
            self.intervals.add(iv)
            self.total_length += (iv[1] - iv[0])

    def contains(self, l, r):  # noqa: E741
        """Check if [l, r) is fully covered by existing intervals."""
        if l >= r:
            return True
        i = self._find_left(l)
        if i >= len(self.intervals):
            return False
        il, ir = self.intervals[i]
        if not (il <= l < ir):
            return False
        while l < r and i < len(self.intervals):
            il, ir = self.intervals[i]
            if il > l:
                return False
            if ir >= r:
                return True
            l = ir  # noqa: E741
            i += 1
        return False

    def difference(self, l, r) -> list[tuple[int, int]]:  # noqa: E741
        """Return list of intervals in [l, r) not covered by the set."""
        uncovered = []
        if l >= r:
            return uncovered
        pos = l
        i = self._find_left(l)
        while pos < r:
            if i >= len(self.intervals):
                uncovered.append((pos, r))
                break
            il, ir = self.intervals[i]
            if ir <= pos:
                i += 1
                continue
            if il > pos:
                uncovered.append((pos, min(il, r)))
            pos = max(pos, ir)
            if pos >= r:
                break
            i += 1
        return uncovered

    def total(self) -> int:
        """Return total covered length."""
        return self.total_length

    def __repr__(self):
        return f"IntervalSet({list(self.intervals)}, total={self.total_length})"
